package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/climbing-stairs/
 */
public class P70 {


    public int climbStairs(int n) {
        int[] dp=new int[n+1];      //dp[i]表示爬到第i阶有多少种爬法
        dp[0]=1;
        dp[1]=1;
        for (int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    //进阶版：改为一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
    //完全背包问题，走的阶数为物品，楼顶为背包
    public int climbStairs2(int n) {
        int[] dp=new int[n+1];      //dp[i]表示爬到第i阶有多少种爬法
        dp[0]=1;
        int m=2;                    //每次可走1阶/2阶/3阶.....m阶
        for(int i=1;i<=n;i++){      //求排列，先遍历背包容量再遍历物品
            for(int j=1;j<=m;j++){
                if(i-j>=0) dp[i]+=dp[i-j];
            }
        }
        return dp[n];
    }
}
